package simple;

// class Solution {
//     /*
//     1.两边向中间读，比对相等
//         拷贝到数组+双指针
//     */
//     public boolean isPalindrome(ListNode head) {
//         //剪枝
//         if(head != null && head.next == null){
//             return true;
//         }
//         ListNode cur = head;

//         List<Integer> nums = new ArrayList<Integer>();

//         while(cur != null ){
//             nums.add(cur.val);
//             cur = cur.next;
//         }
//         int l = 0;
//         int r = nums.size() - 1;
//         while(l < r){
//             if(! nums.get(l).equals(nums.get(r))){
//                 return false;
//             }
//             l++;
//             r--;
//         }
//         return true;
//     }
// }

// class Solution {
//     /*
//     2.顺序读与逆序读一样
//         前序遍历与后序遍历比对
//     */

//     List<Integer> a = new ArrayList<Integer>();
//     List<Integer> b = new ArrayList<Integer>();

//     public boolean isPalindrome(ListNode head) {
//         //剪枝
//         if(head != null && head.next == null){
//             return true;
//         }



//         tarverse(head);

//         return a.equals(b);


//     }
//     public void tarverse(ListNode head){

//         if(head == null){
//             return;
//         }

//         a.add(head.val);

//         tarverse(head.next);

//         b.add(head.val);
//     }
// }

class Solution234 {
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
    /*
    3.两边往中间读思路,快慢指针+链表翻转,时间复杂度O(1)
        快慢指针找到中点(后一个点开始翻转)
        三指针翻转
        持有原头节点，后半段翻转后同样持有头节点
        比对
    */
    public boolean isPalindrome(ListNode head) {
        // 边界情况：空链表或只有一个节点的链表是回文
        if (head == null || head.next == null) {
            return true;
        }

        // 步骤 1: 使用快慢指针找到前半部分的尾节点
        ListNode firstHalfEnd = findEndOfFirstHalf(head);

        // 步骤 2: 反转后半部分链表，并得到后半部分的新头节点
        ListNode secondHalfStart = reverseList(firstHalfEnd.next);

        // 步骤 3: 比较前半部分和反转后的后半部分
        ListNode p1 = head;                      // 前半部分的头指针
        ListNode p2 = secondHalfStart;           // 后半部分的头指针
        boolean result = true;                   // 默认结果为 true
        while (p2 != null) { // 以p2为准，因为奇数链表后半段更短
            if (p1.val != p2.val) {
                result = false; // 发现不匹配
                break;          // 立刻退出比较
            }
            p1 = p1.next;
            p2 = p2.next;
        }

        // 步骤 4: (可选，但良好习惯) 恢复原始链表，将后半部分再反转回来
        firstHalfEnd.next = reverseList(secondHalfStart);

        return result;
    }

    /**
     * 辅助函数：使用快慢指针找到链表前半部分的尾节点
     */
    private ListNode findEndOfFirstHalf(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        // 当 fast 走到末尾时，slow 正好在前半部分的末尾
        // (对于奇数链表，slow会停在正中间)
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    /**
     * 辅助函数：使用迭代法反转一个链表，并返回新的头节点
     */
    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }
}